package org.example.myleet.p959;

public class Solution {

    private static int BLANK = 0;
    private static int SLASH = 1;
    private static int TRANS_SLASH = 2;

    /**
     * 5 ms
     * 将每个单元格预先分为4个区域，上右下左顺时针分别为0、1、2、3四个区域
     * 当空白时，4个区域全部连接；当斜线时，0、3连接，1、2连接；当反斜线时，0、1连接，2、3连接
     * 每个格子对应方向的区域直接连接右、下两个方向的格子的对应区域
     * 例如向下时，2连接下面格子的0区域；向右时，1连接右边格子的3区域
     * 最后观察并查集中有多少个独立的root即可，也可以边算边用count记录剩余区域个数，每次发生真正融合都--count，最终的count即为连通分量个数
     */
    public int regionsBySlashes(String[] grid) {
        //初始化，先解析格子
        int N = grid.length;
        int[][] matrix = new int[N][N];
        for (int i=0; i<N; i++) {
            int j = 0;
            do {
                char c = grid[i].charAt(j);
                if (' ' == c) {
                    matrix[i][j] = BLANK;
                } else if ('/' == c) {
                    matrix[i][j] = SLASH;
                } else if ('\\' == c) {
                    matrix[i][j] = TRANS_SLASH;
                }
                ++j;
            } while (j<grid[i].length());
        }
        //由于每个格子被划分为上右下左顺时针分别为0、1、2、3四个区域，因此并查集长度为4 * N * N
        int regionsAmount = 4 * N * N;
        UnionFind uf = new UnionFind(regionsAmount);
        for (int i=0; i<matrix.length; i++) {
            for (int j=0; j<matrix[i].length; j++) {
                int baseIdx = 4 * (i * matrix.length + j);
                if (BLANK == matrix[i][j]) {
                    //当空白时，4个区域全部连接
                    uf.union(baseIdx, baseIdx+1);
                    uf.union(baseIdx+1, baseIdx+2);
                    uf.union(baseIdx+2, baseIdx+3);
                } else if (SLASH == matrix[i][j]) {
                    //当斜线时，0、3连接，1、2连接
                    uf.union(baseIdx, baseIdx+3);
                    uf.union(baseIdx+1, baseIdx+2);
                } else if (TRANS_SLASH == matrix[i][j]) {
                    //当反斜线时，0、1连接，2、3连接
                    uf.union(baseIdx, baseIdx+1);
                    uf.union(baseIdx+2, baseIdx+3);
                }
                if (i<matrix.length-1) {
                    //向下时，2连接下面格子的0区域
                    int downIdx = 4 * ((i+1) * matrix.length + j);
                    uf.union(baseIdx+2, downIdx);
                }
                if (j<matrix[i].length-1) {
                    //向右时，1连接右边格子的3区域
                    int rightIdx = 4 * (i * matrix.length + (j+1));
                    uf.union(baseIdx+1, rightIdx+3);
                }
            }
        }
        return uf.count;
    }

    static class UnionFind {
        int[] parent;
        int count;

        public UnionFind(int len) {
            parent = new int[len];
            for (int i=0; i<len; i++) {
                parent[i] = i;
            }
            count = len;
        }

        public int find(int x) {
            int p = parent[x];
            if (p != parent[p]) {
                parent[x] = find(p);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            //发生真正融合
            parent[rootX] = rootY;
            --count;
        }
    }
}
